package summary;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/19 10:24
 */
public class Title672 {

    /**
     * 1、将所有灯泡的状态反转（即开变为关，关变为开）
     * 2、将编号为偶数的灯泡的状态反转
     * 3、将编号为奇数的灯泡的状态反转
     * 4、将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, ...)
     * @param n
     * @param presses
     * @return
     */
    public static int flipLights(int n, int presses) {
        if (n == 0) {
            return 0;
        } else if (presses == 0) {
            return 1;
        }
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        StringBuilder begin = new StringBuilder();
        if (n > 6) {
            n = 6;
        }
        if (presses >= 2) {
            presses = 2;
        }
        for (int i = 1; i <= n; i++) {
            begin.append(1);
        }
        String string = begin.toString();
        queue.offer(string);
        int size = 1;
        while (presses-- > 0 && !queue.isEmpty()) {
            int temp = size;
            size = 0;
            for (int e = 0; e < temp; e++) {
                String state = queue.poll();
                String result;
                //状态1
                StringBuilder s1 = new StringBuilder();
                for (int i = 0; i < state.length(); i++) {
                    if (state.charAt(i) == '0') {
                        s1.append('1');
                    } else {
                        s1.append('0');
                    }
                }
                result = s1.toString();
                if (presses == 0) {
                    visited.add(result);
                }
                size++;
                queue.offer(result);
                //状态2
                StringBuilder s2 = new StringBuilder();
                for (int i = 0; i < state.length(); i++) {
                    if (i % 2 == 0) {
                        s2.append(state.charAt(i));
                    } else {
                        if (state.charAt(i) == '0') {
                            s2.append('1');
                        } else {
                            s2.append('0');
                        }
                    }
                }
                result = s2.toString();
                if (presses == 0) {
                    visited.add(result);
                }
                size++;
                queue.offer(result);
                //状态3
                StringBuilder s3 = new StringBuilder();
                for (int i = 0; i < state.length(); i++) {
                    if (i % 2 != 0) {
                        s3.append(state.charAt(i));
                    } else {
                        if (state.charAt(i) == '0') {
                            s3.append('1');
                        } else {
                            s3.append('0');
                        }
                    }
                }
                result = s3.toString();
                if (presses == 0) {
                    visited.add(result);
                }
                size++;
                queue.offer(result);
                //状态4
                StringBuilder s4 = new StringBuilder();
                int k = 0;
                for (int i = 0; i < state.length(); i++) {
                    if (i == 3 * k) {
                        if (state.charAt(i) == '0') {
                            s4.append('1');
                        } else {
                            s4.append('0');
                        }
                        k++;
                    } else {
                        s4.append(state.charAt(i));
                    }
                }
                result = s4.toString();
                if (presses == 0) {
                    visited.add(result);
                }
                size++;
                queue.offer(result);
            }
        }
        return visited.size();
    }

    public static void main(String[] args) {
        flipLights(3, 2);
    }
}
